11. 集合底层实现及泛型

Set 底层实现

HashSet

内部实现是 HashMap，add 方法添加到 HashSet 的元素是作为 HashMap 的 key，所有的 value 共享同一个 Object 类型的常量 PRESENT。

LinkedHashSet

内部实现是 LinkedHashMap，add 方法添加到 LinkedHashSet 的元素是作为 LinkedHashMap 的 key，所有的 value 共享同一个 Object 类型的常量 PRESENT。

TreeSet

内部实现是 TreeMap，add 方法添加到 TreeSet 的元素是作为 TreeMap 的 key，所有的 value 共享同一个 Object 类型的常量 PRESENT。

Iterator

java.util.Iterator 接口常用的方法共有三个。1. hasNext() 2. next() 3.remove()。所有的 Collection 系列的集合中都包含一个 iterator 方法。每一种 Collection 系列集合的实现类【例如 ArrayList，Veactor，LinkedList……】中都有一个内部类实现了 Iterator 接口，这么做的目的就是让每个集合的迭代器只为当前集合服务。

ArrayList

内部底层实现为数组。如果是 JDK 1.8 的时候，初始化是一个长度为 0 的数组。如果是 JDK 1.6 的时候，初始化是一个长度为 10 的数组。如果是 JDK 1.7 的时候，初始化是一个长度为 0 的数组。即从 1.7 开始从原来的初始化为 10 个元素变为 0 个元素。

当元素超过初始容量的时候如何扩容? 当 JDK 版本为 1.7 或者 1.8 的时候，因为一开始是空数组，那么第一次将扩展为长度为 10 的数组。超过之后，再次扩容为原来容量的 1.5 倍。删除元素时候，数组并不会缩小，在 ArrayList 中可以使用 trimToSize() 方法来调整大小为当前使用的大小。

LinkedList

内部底层实现为链表，add 方法默认将元素添加到链表的尾部。

HashMap

JDK 1.7 之前，底层实现为数组 + 链表。数组的初始化长度为 16，如果手动指定那么长度也是2的n次方，如果不是那么回自动纠正接近 2 的 n次方的值。当数组的长度达到 16 * 0.75 的时候就会扩容。

JDK 1.8 开始，HashMap 的底层设计变为数组 + 链表或者数组 + 红黑树。这么做的原因是当数组某个位置的链表较长时，查询效率还是很低。现在设计为当数组某个 index 下的链表节点个数较少时（8个以内），那么就保持链表，否则如果超过 8 个，那么就考虑把链表转换为一颗红黑树。并不是链表节点数量达到 8 个之后理解转换为红黑色，还取决于现目前扩容的数组的长度是否达到 64, 如果没有达到 64，那么就进行数组扩容，直到大于 64 为止。其余的特性，例如，默认加载因子还是为 0.75，默认初始化长度还是 16 等，都和 1.8 之前的版本的一样。

TREEIFY_THRESHOLD: 从链表变成红黑树的阀值, 值为 8。

MIN_TREEIFY_CAPACITY: 从链表变成红黑树的阀值，数组的长度要求必须大于 64。

即只有当满足两个条件，HashMap 中的链表才会转变为红黑树。链表长度大于 8，数组长度扩容至 64 以上。

当删除节点时，红黑树的节点数量少于 6 个，那么就会从红黑树转化为链表。UNTREEIFY_THRESHOLD 小于等于 6。

泛型

概念

参数化的类型。在设计类或者接口的时候，某个属性或者方法行参的类型不清楚是什么的时候，我们可以将整个不清楚的类型设计为泛型，即类型形参。

package com.itguigu.set;

public class TestGeneric {
	// a, b 为数据形参
	public int getMax(int a, int b) {
		return a>b?a:b;
	}
}

// T 为类型形参
class MyArrayList<T> {
	private T[] arr;
}

泛型类, 泛型接口

当泛型做为形参时，需要注意的几个问题？

泛型形参可能有多个
泛型形参一般都是一个大写字母
泛型实参必须是引用数据类型，不能是基本数据类型。如果是基本数据类型，需要使用其对应的包装类。
泛型类或泛型接口上的泛型形参，可以在该类或者接口中当做属性的类型，方法的形参类型，方法的返回值类型，局部变量的类型都可以。但是不能作为 “静态” 成员的相关类型。
泛型行参可以设置上限，也就说可以使用 extends 来设置一组类型的泛型，示例如下

class XueYuan<T extends Number>{
	private T score;
}

class TestXueYuan{
	public void test() {
		XueYuan<Double> xueYuan0 = new XueYuan<Double>();
		XueYuan<Integer> xueYuan1 = new XueYuan<Integer>();
		XueYuan<Float> xueYuan2 = new XueYuan<Float>();
	}
}

现目前学到的知识中，哪些不支持基本数据类型？

集合
泛型

泛型类或泛型接口上的泛型形参什么时候具体化，即什么时候指定泛型实参？

创建对象，实例化的时候
在实现接口，或者继承类的时候

package com.itguigu.set;


public class TestGeneric {
	public static void main(String[] args) {
        //1. 创建对象，实例化的时候
		MyArrayList<String> myArrayList = new MyArrayList<String>();	
	}
	
	// a, b 为数据形参
	public int getMax(int a, int b) {
		return a>b?a:b;
	}
}

// T 为类型形参
class MyArrayList<T> {
	private T[] arr;
}

// 2.在实现接口，或者继承类的时候
class Student implements Comparable<Student>{

	@Override
	public int compareTo(Student o) {  // 这里指定泛型之后，就是指定泛型的类型了，不是之前 Object
		return 0;
	}	
}

泛型练习

练习1：将本组学员的姓名（String）存储到一个 ArrayList 中，并且用 foreach 和 Iterator 分别遍历

package com.itguigu.set;

import java.util.ArrayList;
import java.util.Iterator;

public class TestExec1 {
	public static void main(String[] args) {
		// 1.7 之前需要这么写
		// ArrayList<String> list = new ArrayList<String>();
		// 1.7 之后可以省略后面的类型，只保留<>
		// ArrayList<String> list = new ArrayList<>();
		ArrayList<String> list = new ArrayList<>();
		
		list.add("name1");
		list.add("name2");
		list.add("name3");

		for (String name : list) {
			System.out.println(name);
		}
		
		Iterator<String> iterator = list.iterator();
		while (iterator.hasNext()) {
			String string = iterator.next();
			System.out.println(string);
		}
	}
}

练习2：将学员对象（Students）存储到一个 ArrayList 中，并且用 foreach 和 Iterator 分别遍历

package com.itguigu.set;

import java.util.ArrayList;
import java.util.Iterator;

public class TestExec2 {
	public static void main(String[] args) {
        // 为自定义类型
		ArrayList<Students> list = new ArrayList<>();
		
		list.add(new Students(1, "zhangsan", 90));
		list.add(new Students(2, "lisi", 94));
		list.add(new Students(3, "wangwu", 88));
		
		Iterator<Students> iterator = list.iterator();
		while (iterator.hasNext()) {
			Students students = iterator.next();
			System.out.println(students.getId() + "," + students.getName());
		}
		
	}
}

class Students{
	private int id;
	private String name;
	private int score;
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public int getScore() {
		return score;
	}
	public void setScore(int score) {
		this.score = score;
	}
	@Override
	public String toString() {
		return "Students [id=" + id + ", name=" + name + ", score=" + score + "]";
	}
	public Students(int id, String name, int score) {
		super();
		this.id = id;
		this.name = name;
		this.score = score;
	}
	public Students() {
		super();
	}
}

练习3：将本组学员的姓名和他的朋友们存储到一个 HashMap 真，并且使用 entrySet 进行遍历显示。

package com.itguigu.set;

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class TestExec3 {
	public static void main(String[] args) {
		HashMap<String, String[]> map = new HashMap<>();
		
		map.put("zhangsan", new String[] {"lisi", "wagnwu"});
		map.put("liuliu", new String[] {"wangwang", "sansna"});
		map.put("22", null);
		
		Set<Entry<String,String[]>> entrySet = map.entrySet();
		for (Entry<String, String[]> entry : entrySet) {
			String key = entry.getKey();
			System.out.println(key);
			
			String[] value = entry.getValue();
			if (value!=null) {
				for (String name: value){
					System.out.println("\t" + name);
				}
			}else {
				System.out.println("");
			}
			
		}
		/**
		22

		zhangsan
			lisi
			wagnwu
		liuliu
			wangwang
			sansna
		 */
	}
}

package com.itguigu.set;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class TestExec3 {
	public static void main(String[] args) {
		HashMap<String, ArrayList<String>> map = new HashMap<>();
		
		ArrayList<String> list1 = new ArrayList<>();
		list1.add("zhangzhang");
		list1.add("sansan");
		
		map.put("zhangsan", list1);
		
		ArrayList<String> list2 = new ArrayList<>();
		list2.add("lisi");
		list2.add("zhaoliu");
		
		map.put("wangwu", list2);
		
		Set<Entry<String,ArrayList<String>>> entrySet = map.entrySet();
		for (Entry<String, ArrayList<String>> entry : entrySet) {
			String key = entry.getKey();
			System.out.println(key);
			
			ArrayList<String> value = entry.getValue();
			
			for (String name : value) {
				System.out.println("\t" + name);
			}
			
		}
	}
}

泛型方法

为什么要有方法？

当一个方法是一个静态方法，而该方法的行参类型或返回值类型不确定，那么可以将这个方法设计为一个泛型行参。（最常用）
当某个类不是泛型类，而它的某个非静态方法想要用泛型，那么也可以为这个方法设计（声明）泛型行参
当某个类是泛型类，但是某个非静态方法不想用类上的泛型行参，而是想要单独设计一个自己的泛型，那么也可以。

泛型方法的泛型行参列表什么时候确定？当调用这个方法的时候，传了对应的实参，就确定了泛型的类型。

常见的泛型方法：

Arrays.asList

package com.itguigu.set;

import java.util.Arrays;
import java.util.List;

public class TestExec3 {
	public static void main(String[] args) {
		List<String> asList = Arrays.asList("java", "python");
		 // class java.util.Arrays$ArrayList
		System.out.println(asList.getClass());
		 // 注意，asList 的返回值不是 java.util.ArrayList, 而是 java.util.Arrays 中的一个 ArrayList 
		 // asList.add("!!!"); 因为不是 java.util.ArrayList, 所以不能有 add 操作。asList 返回的是一个只读的类型。
	}
}

Arrays.copyOf

package com.itguigu.set;

import java.util.Arrays;

public class TestExec3 {
	public static void main(String[] args) {
		String[] aa = new String[] {"lisi", "wagnwu", "iuqoe"};
		String[] copyOf = Arrays.copyOf(aa, 2);
		for (String string : copyOf) {
			System.out.println(string); // lisi wagnwu
		}
	}
}